package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 快速排序</p>
 *
 * @author tanzc
 * @date 2021/12/23
 **/
public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int num = 100000000, max = num * 5;
        int[] arr = ArrayUtils.random(num, max);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);

        System.out.print("快速排序-----time: ");
        Date start = new Date();
        quickSort.quick(arr1, 0, num - 1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
    }

    /**
     * 快速排序采用了分治法思想，每轮排序找出一个元素的最终位置，该元素可以将排序序列分为两部分
     * 再分别对两部分进行快速排序
     * @param arr
     * @param l
     * @param r
     */
    public void quick(int[] arr, int l ,int r) {
        if (l < r) {
            int index = part(arr, l, r);
            quick(arr, l, index - 1);
            quick(arr, index + 1, r);
        }
    }

    /**
     * 一轮快排, 确定一个元素的最终位置并返回
     * 根据此位置对排序分区
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public int part(int[] arr, int l, int r) {
        int base = arr[l];
        while (l < r) {
            // base选为arr[l]，因此循环内，先从r侧循环，再从l侧循环
            while (l < r && arr[r] >= base) {
                r--;
            }
            arr[l] = arr[r];
            while (l < r && arr[l] <= base) {
                l++;
            }
            arr[r] = arr[l];
        }
        // l 即为base的最终位置
        arr[l] = base;
        return l;
    }
}
